package com.yaoli.ajob;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * unsolved
 * Created by will on 2017/4/11.
 */
public class _368_LargestDivisibleSubset {
    public static void main(String[] args) {
        _368_LargestDivisibleSubset largestDivisibleSubset = new _368_LargestDivisibleSubset();
        int nums []= {2,3,4,9,8};
//        int nums []= {3,4,6,8,12,16,32};
        List<Integer> list = largestDivisibleSubset.largestDivisibleSubset3(nums);
        System.out.println("");
    }

    /**
     * 动态规划算法
     *
     * 解决思路，新建一个 ArrayList的 类型数组 lists
     *
     * 每一个都保存了 前一个的最多 的约数
     *
     * 只要能够整除 就将当前的 长度和 之前的强度比较
     *
     * 如果 大于就行
     *
     * 并且利用一个指针记录 最长值
     * @param nums
     * @return
     */
    public List<Integer> largestDivisibleSubset3(int[] nums) {
        ArrayList<Integer> lists [] = new ArrayList[nums.length];
        ArrayList<Integer> list = new ArrayList<Integer>();
        if(nums.length < 1){
            return list;
        }
        list.add(nums[0]);
        lists[0] = list;

        Arrays.sort(nums);

        int maxIndex = 0;

        for (int i = 1; i < nums.length; i++) {
            if(lists[i] == null){
                lists[i] = new ArrayList<Integer>();
            }

            for (int j = i - 1; j >= 0; j--) {
                if(nums[i] % nums[j] == 0){
                    if(lists[i].size() < lists[j].size()){
                        lists[i].clear();
                        lists[i].addAll(lists[j]);
                    }
                }
            }

            lists[i].add(nums[i]);

            if(lists[i].size() > lists[maxIndex].size()){
                maxIndex = i;
            }
        }


        return lists[maxIndex];
    }
    public List<Integer> largestDivisibleSubset(int[] nums) {
        List<Integer> res = new ArrayList<Integer>();
        if (nums == null || nums.length == 0) return res;
        Arrays.sort(nums);


        int[] dp = new int[nums.length];
        dp[0] = 1;

        //for each element in nums, find the length of largest subset it has.
        for (int i = 1; i < nums.length; i++){
            for (int j = i-1; j >= 0; j--){
                if (nums[i] % nums[j] == 0){
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                }
            }
        }

        //pick the index of the largest element in dp.
        int maxIndex = 0;
        for (int i = 1; i < nums.length; i++){
            maxIndex = dp[i] > dp[maxIndex] ?  i :  maxIndex;
        }

        //from nums[maxIndex] to 0, add every element belongs to the largest subset.
        int temp = nums[maxIndex];
        int curDp = dp[maxIndex];
        for (int i = maxIndex; i >= 0; i--){
            if (temp % nums[i] == 0 && dp[i] == curDp){
                res.add(nums[i]);
                temp = nums[i];
                curDp--;
            }
        }
        return res;
    }




    public List<Integer> largestDivisibleSubset2(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> table=new LinkedList<List<Integer>>();
        List<Integer> list=new LinkedList<Integer>();
        if(nums.length==0){
            return list;
        }
        list.add(nums[0]);
        table.add(list);
        for(int i=1;i<nums.length;i++){
            boolean mark=true;
            int len=0;
            int cur=-1;
            for(int j=i-1;j>=0;j--){
                if(nums[i]%nums[j]==0){
                    mark=false;
                    if(table.get(j).size()>len){
                        len=table.get(j).size();
                        cur=j;
                    }
                }
            }
            if(mark){
                List<Integer> temp=new LinkedList<Integer>();
                temp.add(nums[i]);
                table.add(temp);
            }else {
                List<Integer> temp=new LinkedList<Integer>(table.get(cur));
                temp.add(nums[i]);
                table.add(temp);
            }
        }
        int mark=0;
        for(int i=0;i<table.size();i++){
            if(table.get(i).size()>table.get(mark).size()){
                mark=i;
            }
        }
        return table.get(mark);
    }
}
